Object models are often stored in computer systems in the form of surfaces. The process of displaying the object (corresponding to the object model) generally requires rendering, which usually refers to mapping the object model onto a two dimensional surface. At least when the surfaces are curved, the surfaces are generally subdivided or decomposed into triangles in the process of rendering the images.
A cubic parametric curve is defined by the positions and tangents at the curve's end points. A Bezier curve, as shown in FIG. 5 for example, is defined by a geometry matrix of four points (P1–P4) that are defined by the intersections of the tangent vectors at the end points of the curve. Changing the locations of the points changes the shape of the curve.
Cubic curves may be generalized to bicubic surfaces by defining cubic equations of two parameters, s and t. In other words, bicubic surfaces are defined as parametric surfaces where the (x,y,z) coordinates in a space called “world coordinates” (WC) of each point of the surface are functions of s and t, defined by a geometry matrix P comprising 16 control points (FIG. 5).
While the parameters s and t describe a closed unidimensional interval (typically the interval [0,1]) the points (x,y,z) describe the surface:
x=f(s,t), y=g(s,t), z=h(s,t) sε[0,1], t ε[0,1], where ε represents an interval between the two coordinates in the parenthesis.
The space determined by s and t, the bidimensional interval [0,1]x[0,1] is called “parameter coordinates” (PC). Textures described in a space called “texture coordinates” (TC) that can be two or even three dimensional are described by sets of points of two ((u,v)) or three coordinates ((u,v,q)). The process of attaching a texture to a surface is called “texture—object association” and consists of associating u, v and q with the parameters s and t via some function:u=a(s,t) v=b(s,t) (and q=c(s,t))
FIGS. 1A and 1B are diagrams illustrating a process for rendering bicubic surfaces. As shown in FIG. 1A, the principle used for rendering such a curved surface 10 is to subdivide it into smaller four sided surfaces or tiles 12 by subdividing the intervals that define the parameters s and t. The subdivision continues until the surfaces resulting from subdivision have a curvature, measured in WC space that is below a predetermined threshold. The subdivision of the intervals defining s and t produces a set of numbers {si} i=1,n and {tj} j=1,m that determine a subdivision of the PC. This subdivision induces a subdivision of the TC, for each pair (si,tj) we obtain a pair (ui,j, vi,j) (or a triplet (ui,j,vi,j, qi,j)). Here ui,j=a(si,tj), vi,j=b(si,tj), qi,j=c(si,tj). For each pair (si,tj) we also obtain a point (called “vertex”) in WC, Vi,j (f(si,tj),g(si,tj),h(si,tj)). A special type of texture, called displacement map having the pair (p,r) as coordinates can be used to generate special lighting effects. For each pair (si,tj) we also obtain a pair (pi,j ri,j) that index a displacement value (dxi,j, dyi,j, dzi,j). for the vertex Vi,j.
This process is executed off-line because the subdivision of the surfaces and the measurement of the resulting curvature are very time consuming. As shown in FIG. 1B, when all resulting four sided surfaces (tiles) 12 is below a certain curvature threshold, each such resultant four-sided surface 12 is then divided into two triangles 14 (because they are easily rendered by dedicated hardware) and each triangle surface gets the normal to its surface calculated and each triangle vertex also gets its normal calculated. The normals are used later on for lighting calculations.
Furthermore, each vertex or triangle plane normal needs to be transformed when the surface is transformed in response to a change of view of the surface, a computationally intensive process that may need dedicated hardware. Also, there is no accounting for the fact that the surfaces are actually rendered in a space called “screen coordinates” (SC) after a process called “projection” which distorts such surfaces to the point where we need to take into consideration the curvature in SC, not in WC.
The state of the art in today's hardware architecture for rendering relies overwhelmingly on triangle databases such as meshes, strips, fans. The current state of the art in the computer graphics industry is described in FIG. 2, which shows an architecture of a conventional computer graphics system, including the architecture of a graphics processing unit (GPU). A CPU 1, executes a software application in the form of a game play or a physical or chemical simulation, etc., in which objects to be rendered are represented as triangle meshes in an object database stored in memory. The triangle meshes are transmitted over an accelerated graphics port (AGP) bus 6 to the GPU 5, which is typically part of a display adapter (video card). The AGP bus 6 is a high-speed port that is designed for the display adapter only to provide a direct connection between the card and memory. The GPU 5 includes a transform unit 2, a lighting unit 3 and a renderer unit 4.
The object modeling in the application is executed on parametric surfaces such as nurbs, Bezier, splines, and the surfaces are subdivided or tessellated off-line and stored as triangle vertices in a triangle database by means of commercially available tools, such as the Alias suite. The triangle vertices are then transmitted from the CPU 1 (the triangle server) to the GPU 5 (the rendering engine) at the time for rendering. Previous attempts to execute the tessellation in hardware in real-time have not been successful because of the severe limitations of the implementation so the current state of the art has been off-line tessellation.
Unfortunately, the off-line tessellation produces a fixed triangulation that may exhibit an excessively large number of very small triangles when the object is far away. Triangle rendering in this case is dominated by the processing of vertices (transformation, lighting) and by the triangle setup (the calculation of the color and texture gradients). Since triangles may reduce to a pixel or less, it is obvious that this is an inefficient treatment.
Conversely, when the object is very close to the viewer, the composing triangles may appear very large and the object looses its smoothness appearance, looking more like a polyhedron.
The increase in the scene complexity has pushed up the number of triangles, which has pushed up the demands for higher bus bandwidth. For example, the bus 6 that connects the CPU 1 with the GPU 5 has increased 8× in frequency, from AGP 1× to AGP 8× in the PC space in the last few years. There are physical constraints in terms of signal propagation that preclude the continuation of the frequency increase in bus design.
With the advent of faster arithmetic it has become possible to change the current architecture such that the CPU 1 will serve parametric patches and the renderer 5 will triangulate such patches in real-time. There are very few past attempts of implementing real-time tesselation in hardware. Sun Corporation tried in the mid-80's to implement such a machine. The implementation was based on an architecture described in a paper by Lien, Sheue-Ling, Shantz, Michael, Pratt, Vaughan “Adaptive Forward Differencing for Rendering Curves and Surfaces”, Siggraph '87 Proceedings, pp. 111–118 and in a series of associated patents. The implementation was not a technical and commercial success because it made no good use of triangle based rendering, trying instead to render the surfaces pixel by pixel. The idea was to use adaptive forward differencing in interpolating infinitesimally close parallel cubic curves imbedded into the bicubic. The main drawback was that sometimes the curves were too close together, resulting into pixel overstrikes and other times the curves were too far apart, leaving gaps. Another drawback was that the method is slow.
In the early 90's Nvidia Corporation made an attempt to introduce a biquadric based hardware renderer. The attempt was not a technical and commercial success because biquadrics have an insufficient number of degrees of freedom, all the models use bicubics, none of the models uses biquadrics.
More currently, Henry Moreton from Nvidia has resurrected the real-time tesselation unit described in the U.S. Pat. No. 6,597,356 entitled “Integrated Tesselator in a Graphics Processing Unit,” issued Jul. 22, 2003. Moreton's invention doesn't directly tesselate patches in real-time, but rather uses triangle meshes pre-tesselated off-line in conjunction with a proprietary stitching method that avoids cracking and popping at the seams between the triangle meshes representing surface patches. His tesselator unit outputs triangle databases to be rendered by the existing components of the 3D graphics hardware.
Accordingly, what is needed is a system and method for performing tessellation in real-time. The present invention addresses such a need.